"NIPS Neural Information Processing Systems 8-11th December 2014, Montreal, Canada",,, "Paper ID:","1407" "Title:","On Communication Cost of Distributed Statistical Estimation and Dimensionality" Current Reviews First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. This paper investigates the communication cost of distributed estimation for d-dimensional spherical Gaussian distribution with unknown mean and unitary covariance, where the joint distribution is assumed to be a product distribution of each coordinate. The authors generalize previous works on the one-dimensional case in [4] by proposing upper and lower bounds for d-dimensional data on two communication schemes, interactive and simultaneous communication settings, for achieving minimax squared loss. The results establish the tradeoffs between dimensionality and communication cost for distributed estimation. In addition, improved bounds are derived when the unknown mean is s-sparse.

First let us recap the subset selection (SS) scheme proposed by [51]. In the achievability part of Theorem 2.1, our proposed scheme SQKR randomly and independently samples We summarize it in the following corollary: Corollary B.2 The achievability parts of Corollary B.1 and Corollary B.2 follow directly from the analysis of SQKR Note that the red line in Figure 3 can be achieved by RHR. A scheme is consistent if it has vanishing estimation error as n!1 . O (min ( d " e log d, d)) bits of communication to achieve r Similarly, the estimation error of private-coin RHR is characterized below: Corollary B.4 (Private-coin RHR) We implement our mean estimation scheme Subsampled and Quantized Kashin's Response (SQKR) We construct the tight frame by using the random partial Fourier matrices in [36]. It can be shown that the tight frame based on U has Kashin's level K = O (1) . Compare to optimal " -LDP scheme [13] Figure 4: ` SQKR achieves similar performance with significantly communication budgets.